import java.util.ArrayList;
import java.util.List;

public class IntToRoman {

    public String intToRoman1(int num) {
        List<Integer> list = new ArrayList<>();
        while (num != 0) {
            list.add(num % 10);
            num /= 10;
        }
        StringBuilder ans = new StringBuilder();
        String[][] str = {{"I", "V"}, {"X", "L"}, {"C", "D"}, {"M"}};
        for (int i = list.size() - 1; i >= 0; i--) {
            Integer temp = list.get(i);
            if (temp < 4) {
                for (int j = 0; j < temp; j++) {
                    ans.append(str[i][0]);
                }
            } else if (temp == 4) {
                ans.append(str[i][0]);
                ans.append(str[i][1]);
            } else if (temp == 5) {
                ans.append(str[i][1]);
            } else if (temp < 9) {
                ans.append(str[i][1]);
                for (int j = 0; j < temp - 5; j++) {
                    ans.append(str[i][0]);
                }
            } else {
                ans.append(str[i][0]);
                ans.append(str[i + 1][0]);
            }
        }
        return ans.toString();
    }

    public String intToRoman(int num) {
        int[] val = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] op = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < op.length; i++) {
            while (num >= val[i]) {
                ans.append(op[i]);
                num -= val[i];
            }
        }
        return ans.toString();
    }
}
